package leetcode_201_300;

import com.sun.media.sound.SF2GlobalRegion;

public class LeeCode_300 {
    public static void main(String[] args) {
        System.out.println(lengthOfLIS(new int[]{10, 9, 2, 5, 3, 7, 101, 18}));
        System.out.println(lengthOfLIS(new int[]{6,7,8,9,1,2,3,4,5}));
    }
    private static int lengthOfLIS(int[] nums) {
        if (nums.length == 0)
            return 0;
        int n = nums.length;
        int[] dp = new int[n];
        int ans = 1;
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]){
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}
